package leetcode_900;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import helpclass.TreeNode;

/**
 *@author 周杨
 *AllPossibleFullBinaryTrees_894 full节点是 要么是只有2个孩子 要么是0个孩子 问拥有所有N个节点的所有构造情况
 *describe:用递归 AC 70%
 *2018年11月12日 下午2:38:17
 */
public class AllPossibleFullBinaryTrees_894 {
	public static void main(String[] args) {
		AllPossibleFullBinaryTrees_894 test=new AllPossibleFullBinaryTrees_894();
		test.allPossibleFBT(7);
	}
	
	public List<TreeNode> allPossibleFBT(int N) {
		if(N%2==0)
			return new ArrayList<TreeNode>();
        Map<Integer,List<TreeNode>> map=new HashMap<Integer,List<TreeNode>>();
        List<TreeNode> one=new ArrayList<TreeNode>();
        one.add(new TreeNode(0));
        if(N==1) return one;
        map.put(1, one);
        for(int i=3;i<=N;i+=2) {
        	List<TreeNode> now=new ArrayList<TreeNode>();
        	for(int j=1;j<=(i-1)/2;j+=2) {
        		for(TreeNode left:map.get(j)) {
        			for(TreeNode right:map.get(i-1-j)) {
        				TreeNode root=new TreeNode(0);
        				root.left=left;
        				root.right=right;
        				now.add(root);
        			}
        		}
        	}
        	map.put(i, now);
        }
        return map.get(N);
    }
	
	
}
